﻿#include <iostream>

using namespace std;

/*
实现next_permutation
算法：
1. 从后往前找，找到第一个x1,使a[x1]<a[x1+1]
2. 从后往前找，找到第一个x2,使a[x1]<a[x2]
3. 交换a[x1],a[x2], 并且反置a[x1+1 … end]
*/
template<class T>
void swap1( T &x, T &y)
{
	T temp = x;
	x = y;
	y = temp;
}

template<class T>
void Revert( T *arr, int start, int end)
{
	while( start<end )
	{
		T tmp = arr[start];
		arr[start] = arr[end];
		arr[end] = tmp;
		start++;
		end--;
	}
}

int FindFirstX1(int *index, int len)
{
	for( int i=len-1; i>=0; i--)
	{
		if(index[i]<index[i+1])
			return i;
	}
	return -1;
}

int FindFirstX2(int *index, int len, int x1)
{
	for(int i=len-1; i>=0; i--)
	{
		if(index[i]>index[x1])
			return i;
	}
	return -1;
}

void PermuteEasy( char* str)
{
	int len = strlen(str);
	int *index = new int[len];
	int totalCount = 0;

	for( int i=0;i<len; i++)
	{
		index[i]=i;
	}

	char *outPut = new char[len+1];
	outPut[len] = '\0';
	memcpy(outPut, str, len);
	cout<<outPut<<endl;
	totalCount++;

	while(1)
	{
		int x1=FindFirstX1(index, len);
		if( x1<0)
		{
			// finish permutation
			break;
		}
		int x2=FindFirstX2(index, len, x1);
		swap1(index[x1], index[x2]);
		swap1(outPut[x1], outPut[x2]);
		Revert(index, x1+1, len-1);
		Revert(outPut, x1+1, len-1);
		cout<<outPut<<endl;
		totalCount++;
	}
	
	cout<<"total count is "<<totalCount<<endl;
}